from typing import List

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def is_palindrome(s: str) -> bool:
            """判断字符串是否为回文串"""
            return s == s[::-1]
        
        def backtrack(start: int, path: List[str]):
            """回溯函数
            start: 当前开始位置
            path: 当前路径（已分割的子串列表）
            """
            # 如果已经遍历完整个字符串，将当前路径加入结果
            if start == len(s):
                result.append(path[:])
                return
            
            # 尝试从当前位置开始的所有可能分割
            for end in range(start + 1, len(s) + 1):
                # 获取当前子串
                substring = s[start:end]
                # 如果当前子串是回文串，继续回溯
                if is_palindrome(substring):
                    path.append(substring)
                    backtrack(end, path)
                    path.pop()  # 回溯，移除最后添加的子串
        
        result = []
        backtrack(0, [])
        return result

def get_time_complexity():
    """返回算法的时间复杂度分析"""
    return """
    时间复杂度分析：
    1. 最坏情况下，对于长度为n的字符串，有2^(n-1)种可能的分割方式
    2. 对于每种分割方式，需要O(n)的时间来验证回文串
    3. 因此总时间复杂度为O(n * 2^n)
    """

def get_space_complexity():
    """返回算法的空间复杂度分析"""
    return """
    空间复杂度分析：
    1. 递归调用栈的深度最大为n
    2. 存储结果的空间复杂度为O(n * 2^n)
    3. 因此总空间复杂度为O(n * 2^n)
    """ 